﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;
using Sets = Algoritmia.DataStructures.Sets;

namespace Algoritmia.Problems.CoinChange
{
    public class ChangeEnumeratorWithSeenSet<TState, TDecision>
    {
        private readonly Func<Lists.IList<TDecision>> _createList;
        private readonly Func<Sets.ISet<TState>> _createSet;
        private readonly Func<IEnumerable<TDecision>, Lists.IList<TDecision>> _copyList;

        public ChangeEnumeratorWithSeenSet(Func<IEnumerable<TDecision>, Lists.IList<TDecision>> createList = null,
                                           Func<Sets.ISet<TState>> createSet = null)
        {
            _copyList = createList ?? (it => AlgoritmiaFactory.Lists<TDecision>.BuildDefault(it));
            _createList = () => _copyList(new TDecision[] { });
            _createSet = createSet ?? (() => AlgoritmiaFactory.Sets<TState>.Default);
        }

        private IEnumerable<Lists.IList<TDecision>> Backtracking(TState state,
            IMoneyChangeForwardStateSpace<TState,TDecision> space, Lists.IList<TDecision> decisions, Sets.ISet<TState> seen)
        {
           if (space.IsFinal(state))
           {
               yield return _copyList(decisions);
           }
            seen.Add(state);
            foreach (var decision in space.Decisions(state))
            {
                decisions.Add(decision);
                var successor = space.Decide(state, decision);
                if ( !seen.Contains(successor))
                {
                    foreach (var result in Backtracking(successor, space, decisions,seen))
                    {
                        yield return result;
                    }
                }
                decisions.RemoveAt(decisions.Count - 1);
            }
        }

        public IEnumerable<Lists.IList<TDecision>> Enumerate(IMoneyChangeForwardStateSpace<TState,TDecision> stateSpace)
        {
            var decisions = _createList();
            var seen = _createSet();
            var initial = stateSpace.InitialStates.First();
            return Backtracking(initial, stateSpace, decisions,seen);
        }

        public Lists.IList<TDecision> First(IMoneyChangeForwardStateSpace<TState,TDecision> stateSpace)
        {
            return Enumerate(stateSpace).First();
        }
    }
}
